use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;

// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
  pub val: i32,
  pub left: Option<Rc<RefCell<TreeNode>>>,
  pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
          val,
          left: None,
          right: None
        }
    }

    // 通过数组反序列化生成一棵树(一维向量/数组转二叉树)
    pub fn vec1d_to_tree_node(nums: Vec<Option<i32>>) -> Option<Rc<RefCell<Self>>> {
        if nums.is_empty() {
            return None;
        }
        let size = nums.len();
        let mut index = 0;
        let root = Some(Rc::new(RefCell::new(Self::new(nums[0].unwrap()))));
        let mut queue = VecDeque::new();
        queue.push_back(root.clone());
        while !queue.is_empty() {
            let q_size = queue.len();
            for _i in 0..q_size {
                if let Some(x) = queue.pop_front().flatten() {
                    // borrow()方法返回内部包装对象的只读引用。
                    // borrow_mut()返回内部包装对象的可写引用。
                    let mut node = x.borrow_mut();
                    let lseq = 2 * index + 1;
                    let rseq = 2 * index + 2;
                    if lseq < size && nums[lseq].is_some() {
                        node.left = Some(Rc::new(RefCell::new(Self::new(nums[lseq].unwrap()))));
                        queue.push_back(node.left.clone());
                    }

                    if rseq < size && nums[rseq].is_some() {
                        node.right = Some(Rc::new(RefCell::new(Self::new(nums[rseq].unwrap()))));
                        queue.push_back(node.right.clone());
                    }
                }
                index += 1;
            }
        }
        root
    }

    // 将一棵树序列化(literal)成一个数组(二叉树转一维向量/数组)
    pub fn tree_node_to_vec1d(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Option<i32>> {
        if root.is_none() {
            return vec![];
        }
        let mut ans = vec![];
        let mut queue = VecDeque::new();
        queue.push_back(root);
        while !queue.is_empty() {
            let qsize = queue.len();
            for _ in 0..qsize {
                match queue.pop_front().flatten() {
                    Some(x) => {
                        ans.push(Some(x.borrow().val));
                        queue.push_back(x.borrow().left.clone());
                        queue.push_back(x.borrow().right.clone());
                    }
                    None => ans.push(None),
                }
            }
        }
        let size = ans.len();
        for i in (0..size).rev() {
            if ans[i].is_none() {
                ans.pop();
            } else {
                break;
            }
        }
        ans
    }

    pub fn print_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<String>> {
        let n = Self::get_depth(&root);
        let m = (1 << n) - 1;
        let mut queue = vec![];
        let mut grid = vec![vec!["".to_string();m];n];

        if let Some(r) = root {
            queue.push((r, 0, (m - 1) / 2));

            while queue.len() > 0 {
                let mut tmp = vec![];

                for i in 0..queue.len() {
                    let (ref node, row, col) = queue[i];
                    grid[row][col] = format!("{}", node.borrow().val);

                    if let Some(left) = node.borrow_mut().left.take() {
                        tmp.push((left, row + 1, col - (1 << (n - row - 2))));
                    }

                    if let Some(right) = node.borrow_mut().right.take() {
                        tmp.push((right, row + 1, col + (1 << (n - row - 2))));
                    }
                }

                queue = tmp;
            }
        }

        grid
    }

    fn get_depth(root: &Option<Rc<RefCell<TreeNode>>>) -> usize {
        if let Some(r) = root {
            1 + Self::get_depth(&r.borrow().left).max(Self::get_depth(&r.borrow().right))
        } else {
            0
        }
    }


}

// 放这儿前面的也能识别
// use std::rc::Rc;
// use std::cell::RefCell;

// pub mod SolutionPrintTree {}
//
// // 655. 输出二叉树
// impl SolutionPrintTree {
//
//     pub fn print_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<String>> {
//         let n = Self::get_depth(&root);
//         let m = (1 << n) - 1;
//         let mut queue = vec![];
//         let mut grid = vec![vec!["".to_string();m];n];
//
//         if let Some(r) = root {
//             queue.push((r, 0, (m - 1) / 2));
//
//             while queue.len() > 0 {
//                 let mut tmp = vec![];
//
//                 for i in 0..queue.len() {
//                     let (ref node, row, col) = queue[i];
//                     grid[row][col] = format!("{}", node.borrow().val);
//
//                     if let Some(left) = node.borrow_mut().left.take() {
//                         tmp.push((left, row + 1, col - (1 << (n - row - 2))));
//                     }
//
//                     if let Some(right) = node.borrow_mut().right.take() {
//                         tmp.push((right, row + 1, col + (1 << (n - row - 2))));
//                     }
//                 }
//
//                 queue = tmp;
//             }
//         }
//
//         grid
//     }
//
//     fn get_depth(root: &Option<Rc<RefCell<TreeNode>>>) -> usize {
//         if let Some(r) = root {
//             1 + Self::get_depth(&r.borrow().left).max(Self::get_depth(&r.borrow().right))
//         } else {
//             0
//         }
//     }
//
// }


#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_1() {
        // 先构造一个二叉树root:
        let nums = vec![
            Some(1),
            Some(2), Some(3),
            Some(4), None, Some(5), Some(6),
            None, Some(7), None, None, Some(8)
        ];
        let root = TreeNode::vec1d_to_tree_node(nums);

        let ans = TreeNode::tree_node_to_vec1d(root);
        // [Some(1), Some(2), Some(3), Some(4), None, Some(5), Some(6), None, Some(7), None, None, Some(8)]
        println!("ans: \n{:?}", ans);
    }

    #[test]
    fn test_print_tree() {
        // 先构造一个二叉树root: // 用的是例2
        let nums = vec![
            Some(1),
            Some(2), Some(3),
            None, Some(4)
        ];
        let root = TreeNode::vec1d_to_tree_node(nums);

        // let ans = TreeNode::tree_node_to_vec1d(root);
        // println!("ans: \n{:?}", ans);

        // 调用 print_tree // expected type, found module `SolutionFindDuplicateSubtrees`
        // 报错的，不知道为啥？？
        // let ans = SolutionPrintTree::print_tree(root);
        // println!("ans: \n{:?}", ans);

        // 调用 print_tree
        let ans = TreeNode::print_tree(root);
        println!("ans: \n{:?}", ans);
        // ans:
        // [["", "", "", "1", "", "", ""], ["", "2", "", "", "", "3", ""], ["", "", "4", "", "", "", ""]]

    }


}